#include "partitionList.h"

ListNode *partition(ListNode *head, int x) {
    ListNode *out_head;
    ListNode *n, *prev_l, *prev_r;
    out_head = prev_l = prev_r = NULL;
    n = head;
    while (n) {
        ListNode *cur = n;
        n = n->next;
        if (cur->val < x) {
            if (prev_l == NULL) {
                if (out_head) {
                    prev_l = cur;
                    cur->next = out_head;
                    out_head = cur;
                }
                else { // out_head == NULL
                    out_head = prev_l = cur;
                    cur->next = NULL;
                }
            }
            else { // prev_l != NULL
                cur->next = prev_l->next;
                prev_l->next = cur;
                prev_l = cur;
            }
        }
        else { //cur->val >= x
            if (out_head == NULL) {
                out_head = prev_r = cur;
                cur->next = NULL;
            }
            else {
                if (prev_r == NULL) {
                    prev_l->next = cur;
                    prev_r = cur;
                    cur->next = NULL;
                }
                else {
                    prev_r->next = cur;
                    prev_r = cur;
                    cur->next = NULL;
                }
            }
        }
    }
    
    return out_head;
}
